package simple.array;

/**
 * <a href="https://leetcode.cn/problems/number-of-good-pairs/">1512. 好数对的数目</a>
 * 给你一个整数数组 nums 。
 * 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
 * 返回好数对的数目。
 * 示例 1：
 *   输入：nums = [1,2,3,1,1,3]
 *   输出：4
 *   解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
 * 示例 2：
 *   输入：nums = [1,1,1,1]
 *   输出：6
 *   解释：数组中的每组数字都是好数对
 * 示例 3：
 *   输入：nums = [1,2,3]
 *   输出：0
 * 提示：
 *   1 <= nums.length <= 100
 *   1 <= nums[i] <= 100
 * @author 刘学松
 * @date 2023-08-11 10:52
 */
public class 好数对的数目 {
    public int numIdenticalPairs(int[] nums) {
        int[] cnt = new int[101];
        for (int num : nums) {
            cnt[num]++;
        }
        int count = 0;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] > 1) {
                count += count(cnt[i] - 1);
            }
        }
        return count;
    }

    public int count(int n) {
        return (n * n + n) >> 1;
    }
}
